package Main2;

import com.sun.corba.se.spi.activation.TCPPortHelper;

import java.awt.peer.SystemTrayPeer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main13_15 {
    // 手套
    public int findMinimum(int n, int[] left, int[] right) {
        int leftSum = 0;
        int rightSum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            // 左手手套 或者右手手套有一个数量是0，此时就是不能匹配的，所以在取出的时候需要把这个手套取出来
            if (left[i] * right[i] == 0) {
                sum += left[i] + right[i];
            } else {
                leftSum += left[i];
                rightSum += right[i];
                if (leftMin > left[i]) leftMin = left[i];
                if (rightMin > right[i]) rightMin = right[i];
            }
        }
        return Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1 + sum;
    }

    // 查找输入整数二进制中 1 的个数
    public static void main5(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int num = scan.nextInt();
            int count = 0;
            while (num != 0) {
                int a = num % 2;
                if (a == 1) count++;
                num /= 2;
            }
            System.out.println(count);
        }
    }

    // 幸运的袋子
    /*思路：1. 将袋子里的球的号码排序
    *      2. 当一个号码和前边的号码无法组成幸运的袋子，直接break，因为后面的号码肯定比前边的号码数字大于或者等于，也无法构成幸运的袋子
    *      3. 当返回上层递归的时候，需要回溯，继续计算前面的号码和当前位置后面的号码是否可以构成幸运的袋子
    *      特殊情况：a[i] = 1，1和任何数的和都大于它和任何数的积
    * */
    public static void main4(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scan.nextInt();
            }
            Arrays.sort(arr);
            System.out.println(count(arr, n, 0, 0, 1));
        }
    }

    private static int count(int[] arr, int n, int pos, int sum, int multi) {
        int count = 0;
        for (int i = pos; i < n; i++) {
            sum += arr[i];
            multi *= arr[i];
            if (sum > multi) {
                // 如果和 > 积 就说明多了一种构成幸运袋子的方法
                count = count + 1 + count(arr, n, i + 1, sum, multi);
            } else if (arr[i] == 1) {
                // 当 某一个号码 = 1 的时候，此时不能跳出循环 要跳过当前位置继续计算
                count = count + count(arr, n, i + 1, sum, multi);
            } else {
                break;
            }
            sum = sum - arr[i];
            multi = multi / arr[i];
            while (i < n-1 && arr[i] == arr[i+1]) {
                i++;
            }
        }
        return count;
    }

    // 计算日期到天数转换
    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int y = scan.nextInt();
            int m = scan.nextInt();
            int d = scan.nextInt();
            int[] day = {31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
            int sum = 0;
            if (m >= 2) {
                sum += day[m-2];
            }
            sum += d;
            // 判断是否是闰年
            if (((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)) && m > 2) {
                sum += 1;
            }
            System.out.println(sum);
        }
    }

    //跳石板
    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int m = scan.nextInt();
            int[] step = new int[m + 1];
            for (int i = 0; i < m + 1; i++) {
                step[i] = Integer.MAX_VALUE;
            }
            step[n] = 0;
            for (int i = n; i < m; i++) {
                if (step[i] == Integer.MAX_VALUE) {
                    continue;
                }
                List<Integer> list = div(i);
                // j 代表可以一块跳跃几次石板
                // i 代表当前石板的编号
                for (int j : list) {
                    if (i + j <= m && step[i+j] != Integer.MAX_VALUE) {
                        step[i + j] = Math.min(step[i+j], step[i] + 1);
                    } else if (i + j <= m) {
                        step[i + j] = step[i] + 1;
                    }
                }
            }
            if (step[m] == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(step[m]);
            }
        }
    }
    public static List<Integer> div(int num) {
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0) {
                list.add(i);
                if (num / i != i) list.add(num / i);
            }
        }
        return list;
    }

    //参数解析
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String str = scan.nextLine();
            int count = 0;
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch == '"') {
                    do {
                        i++;
                    } while (ch != '"');
                }
                //双引号之外的空格
                if (ch == ' ') count++;
            }
            //空格永远比参数的个数少1
            System.out.println(count + 1);

            //输出参数思路：分几种情况：1.双引号中的空格也得输出，但是引号不输出
            //2. 双引号以外的空格要进行换行
            int flg = 1;
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch == '"') flg ^= 1;
                if (ch != ' ' && ch != '"')
                    System.out.print(ch);
                if (ch == ' ' && flg == 0)
                    System.out.print(ch);
                if (ch == ' ' && flg == 1)
                    System.out.println();
            }
        }
    }
}
